#ifndef _CP_QUAD_TREE_H_
#define _CP_QUAD_TREE_H_

#define MAX_ELE_NUM 1000
#define QUADRANT_RU 1
#define QUADRANT_LU 2
#define QUADRANT_LB 3
#define QUADRANT_RB 4

struct Region 
{
    double up;
    double bottom;
    double left;
    double right;
	Region():up(0),bottom(0),left(0),right(0)
	{

	}
};

struct ElePoint 
{
    double lng;
    double lat;
    //char desc[16];
	char* desc ;
	ElePoint ():lng(0),lat(0)
	{
		desc = new char[16];
	}
	~ElePoint()
	{
		//delete desc;
		//desc = NULL;
	}
};

struct QuadTreeNode 
{
    int depth;
    int is_leaf;
    Region region;
    QuadTreeNode *LU;
    QuadTreeNode *LB;
    QuadTreeNode *RU;
    QuadTreeNode *RB;
    int ele_num;
    ElePoint *ele_list[MAX_ELE_NUM];
	QuadTreeNode():LU(0),LB(0),RU(0),RB(0),depth(0),is_leaf(0)
	{
	}
};

void initNode(QuadTreeNode *node, int depth, Region region);

void insertEle(QuadTreeNode *node, ElePoint ele);

void deleteEle(QuadTreeNode *node, ElePoint ele);

void splitNode(QuadTreeNode *node);

void combineNode(QuadTreeNode *node);

void queryEle(QuadTreeNode tree, ElePoint ele);

void initRegion(Region *region, double up, double bottom, double left, double right);


struct QuadTreeNode *createChildNode(QuadTreeNode *node, double bottom, double up, double left, double right);

int testFunc();
#endif